/**
 * 计数dp-
 *      划分数 与 多重组合
 *  dp[i][j]=dp[i-1][j]+dp[i][j-i]
    1、j个物品分成i份　j>i
        1\ 每份划分都大一等于1 dp[i][j-i] 即至少有一个是最大为 j-i
        2\ 存在一个用0划分 dp[i-1][j]
    
    

 * 1、划分数：
 *      n个一样的球，放在m个篮里，(n<m)求放球方案个数
 *      其中篮子里可以为 空 即 不一定非要用该篮子
 *      111 有两个篮子
 *          1|2
 *          3|0
 *          3 = 3
 *            = 2+1
 *    类似问题：
 *       求整数划分 
 *          5 = 5          —————— f(5,5) 
 *            = 4+1        —————— f(5,4) 
 *            = 3+2         |
 *            = 3+1+1      —————— f(5,3) 
 *            = 2+2+1       |
 *            = 2+1+1+1    —————— f(5,2) 
 *            = 1+1+1+1+1  —————— f(5,1)     
 *      一共：7种
 *      这里5的划分可以看作 将5个果子分在 5个篮子里
 *  所以我们分析整数划分
 *      如上我们要求的是F(5,5)
 *  F(5,5)表示 当max(m1,m2,...,mi)<=m时，我们记n的m划分的个数为f(n,m);
 *      n = m1+m2+...+mi;
 *  (听起来有点像偷换概念 但实际上他们确实是一样的)
 * 
 *  1、n=1时 {1} 一个果子
 *  2、m=1时 划分{1,1,1..} 所有东西放在一个盘子里
 *  3、n=m时 我们看是否将最大的(当前所有果子放在一个盘子里) 分为以下情况
 *          1、包含n,放在m个盘子，这时候一种情况 {n,0000000}
 *          2、不将n全部放在一个盘子里，这时一个盘子里最大的数量果子：n-1
 *          即n得n-1划分
 *          f(n,n) =1 + f(n,n-1);
 *  4、n<m 盘子过多，再多也等于 f(n,n)
 *  5、n>m 包含值是否包含最大值m
 *         1、划分中包含m，那么max{m,x1,x2....xi}即max{m,n-m}
 *              即n-m个盘子里放
 *              f(n-m,n)
 *         2、不包含,最大得为m-1
 *              f(n,m-1)
 * 
 * 1\2为回归条件
 * 3\4为特殊
 * 5为普适
 *  f(n, m)= 1; 　　　　 (n=1 or m=1)
    f(n, m)=f(n, n);　　 (n<m)
    1+ f(n, m-1);   　　 (n=m)
    f(n-m,m)+f(n,m-1); (n>m)

    参考：http://www.cnblogs.com/Inkblots/p/4854227.html
        https://www.cnblogs.com/radiumlrb/p/5797168.html
 */
/**
 * 5|0|0
 * 4|1|0
 * 3|2|0
 * 3|1|1
 * 2|2|1
 */

let res = dp1(5,3);//5
function dp1(m,n){
    let dp = [];
    for(let i=1;i<=m;i++){
        dp[i] = [];
        dp[i][1] =1;
    }

    for(let j=1;j<=n;j++){
        dp[1][j] = 1;
    }

    for(let i=2;i<=m;i++){
        for(let j=2;j<=n;j++){
            if(i>j){
                dp[i][j] = dp[j][j];
            }else if(i==j){
                dp[i][j] = dp[i-1][j] + 1;
            }else{
                dp[i][j] = dp[i][j-i] + dp[i-1][j];
            }
        }
    }
    console.log(dp);
}